INTRODUCTION:

Ad hoc networks are those networks in which every node plays the role of a router and communicates with other nodes. Even if the source and the destination nodes are not within each other’s communication range, data packets are forwarded to the destination by relaying transmission through other nodes that exist between the two nodes. Since no special infrastructure is required, many applications are expected to be developed in adhoc sensor networks in various fields such as military affairs and commerce. Terminals in adhoc network can function not only as end systems but also as intermediate systems (forwarding the packets from other nodes).

Since there are frequent disconnections occurring in the network, the data accessibility is very less in adhoc networks. In order to overcome that we can use a method called replica allocation. In this method, replicas or copies of data will be stored in some machines other than the owner machine. So the data will be always available even if the owner is getting isolated from the network.

In this way, data replication is very effective for improving the data accessibility. On the other hand, mobile hosts generally have poor resources and thus it is usually impossible for mobile hosts to have replicas of all data items in the network.

So the objective of our project is to use some replica allocation algorithms and to find out an efficient replica allocation strategy so that the allocation is optimal considering some parameters such as access frequency and the updation period. There are so many algorithms available for this replication. Some of them are:

SAF (Static Access Frequency) method: Only the access frequency to each data item is taken into account.

E-SAF (Extended Static Access Frequency) method: Access frequency and the PTValue (derived from updation period) are taken into account.

DAFN (Dynamic Access Frequency and Neighborhood) method: The access frequency to each data item and the neighborhood among mobile hosts are taken into account.

DCG (Dynamic Connectivity based Grouping) method: The access frequency to each data item and the whole network topology are taken into account.

The SAF (Static access frequency) is explained in this paper. In static access frequency, only one parameter i.e, the access frequency is taken into account.

To simulate the environment we are using OMNeT++ as the simulation tool. In order to do the file operations C++ is used and to give a graphical interface for the user, Visual Basic 6.0 is being used.

The time stamping property is being used to avoid the inconsistency in the messages. There will be a time stamp value and when the life of a data expires, it will be getting deleted from the network

Fig: Replica allocated for data 1 on another machine

In this paper, we assume an environment where each mobile host has limited memory space for creating replicas. We propose a replica allocation method for improving data accessibility. Moreover, we verify the effectiveness of our proposed method by simulation experiment.

The remainder of the paper is organized as follows. In section II, we give a brief introduction about ad hoc networks. In section III, we introduce some technologies which are used to implement ad hoc networks. In section IV, we propose the model of the system for replica allocation method. In section V, we propose replica allocation method (SAF). In section VI, we introduce the timestamping prpperty. In section VII, we show the results of simulation experiments. Finally, in section VIII, we summarize this paper.

II. RELATED CONCEPTS

Wireless ad hoc networks are formed by devices that are able to communicate with each other using a wireless physical medium without having to resort to a pre-existing network infrastructure. These networks, also known as mobile ad hoc networks (MANETs), can form stand-alone groups of wireless terminals, but (some of) these terminals could also be connected to a cellular system or to a fixed network. A fundamental characteristic of ad hoc networks is that they are able to configure themselves on-the-fly without the intervention of a centralized administration.

Terminals in ad hoc networks can function not only as end systems (executing applications, sending information as source nodes and receiving data as destination nodes), but also as intermediate systems (forwarding packets from other nodes). Therefore, it is possible that two nodes communicate even when they are outside of each other’s transmission ranges because intermediate nodes can function as routers. This is why wireless ad hoc networks are also known as “multi-hop wireless networks”.

Compared to cellular networks, ad hoc networks are more adaptable to changing traffic demands and physical conditions. Also, since the attenuation characteristics of wireless media are nonlinear, energy efficiency will be potentially superior and the increased spatial reuse will yield superior capacity and thus spectral efficiency. These characteristics make ad hoc networks attractive for pervasive communications, a concept that is tightly linked to heterogeneous networks and 4G architectures.

The need for self-configurability and flexibility at various levels (for example, dynamic routing or distributed medium access control) poses many new challenges in wireless ad hoc networks. Cross-layer optimization can significantly improve system performance and thus we will discuss some cross-layer issues.

Depending on their communication range, wireless ad hoc networks can be classified into Body (BAN), Personal (PAN) and Wireless Local (WLAN) Area Networks. A BAN is a set of wearable devices that have a communication range of about 2 m. The second type, PANs, refers to the communication between different BANs and between a BAN and its immediate surroundings (within approximately 10 m). WLANs have communication ranges of the order of hundreds of metres. The main existing technology for implementing BANs and PANs is Bluetooth, while for WLANs the main option is the family of standards IEEE 802.11.

III. ENABILING TECHNOLOGIES

Bluetooth

Bluetooth is a single-chip, low-cost, radio-based wireless network technology suited for ad hoc networks, with communication ranges in the order of 10 m. The single-chip design makes this technology especially useful for small terminals with low energy storage capacity. The physical channels are separated by fast Frequency Hopping Spread Spectrum (FHSS), using 79 carriers in most countries. Hopping slots have duration of 625 us. In order to save power, this technology incorporates a powerful energy management architecture that comprises four different power consumption states.

IEEE 802.11

The family of standards IEEE 802.11 [1] comprises the standards IEEE 802.11, IEEE 802.11b, IEEE 802.11g and IEEE 802.11a, amongst other standards that deal with specific issues such as security, service differentiation, etc. IEEE 802.11 provides wireless and infrared connectivity, but all implemented products use the unlicensed radio bands of 5 GHz (for IEEE 802.11a) and 2.4 GHz (for the rest).

The physical layer offers a number of channels. A set of terminals that use the same channel and are within the communication range of (some of) the other terminals of the set is called Basic Service Set (BSS). The number of physical channels depends on whether BSSs are multiplexed by using FHSS, Direct Sequence Spread Spectrum (DSSS) or Orthogonal Frequency Division Multiplexing (OFDM) techniques. Also, the communication rates per channel depend on the modulation, multiplexing, and forward error correction coding rates, ranging from 1 Mb/s to 54 Mb/s.

In the context of ad hoc networks, users belonging to the same BSS share the medium by means of a distributed random access mechanism called Distributed Coordination Function (DCF), basically a Carrier Sense Medium Access with Collision Avoidance (CSMA/CA) technique.

IV. System model

The system environment is assumed to be an ad hoc network where mobile hosts access data items held by other mobile hosts as the originals. Each mobile host creates replicas of the data items, and maintains the replicas in its memory space. When a mobile host issues an access request to a data item, the request is successful in either case: (i) the mobile host holds the original/ replica of the data item or (ii) at least one mobile host which is connected to the request issue host with a one-hop/multihop link holds the original/replica.

The access frequencies can be calculated by making a counter for each machine and incrementing it each time that machine receives a message. When dividing that value by 10, we will get the access frequencies.

In this system environment, we also make the following assumptions:

Ø We assign a unique host identifier to each mobile host in the system. The set of all mobile hosts in the system is denoted by M= {M0, M1…Mm-1}, where m is the total number of mobile hosts and; Mj (0<=j<m) is a host identifier.

	Machines
Data	M0	M1	M2	M3	M4	M5
D0	0.4	0.4	0.3	0.1	0.2	0.3
D1	0.3	0.5	0.3	0.1	0.1	0.4
D2	0.4	0.7	0.5	0.1	0.2	0.8
D3	0.2	0.3	0.1	0.1	0.1	0.2
D4	0.1	0.1	0.2	0.1	0.3	0.4
D5	0.7	1.1	0.6	0.1	0.3	0.9

Each mobile host moves freely.

Ø Data is handled as a data item which is a collection of data. We assign a unique data identifier to each data item located in the system. The set of all data items is denoted by D= {D0, D1…Dn-1}, where n is the total number of data items and Dj (0<=j<n) is a data identifier. All data items are of the same size, and a particular mobile host as the original holds each data item.

Ø Each mobile host has memory space of C data items for creating replicas excluding the space for the original data item that the host holds.

Ø The data items are not updated. This assumption is for the sake of simplicity. In the abovementioned example of digging investigation, new data is inserted but no update occurs. There are also other applications where the newness of data is not a serious problem, such as weather information.

V. The SAF method

In the SAF method, each mobile host allocates replicas of N data items in descending order of the access frequencies. At the time of replica allocation, a mobile host may not connect to another mobile host which has an original or a replica of a data item that the host should allocate. In this case, the memory space for the replica is retained free.

In the SAF method, mobile hosts do not need to exchange information with each other for replica allocation. Moreover, replica relocation does not occur after each mobile host allocates all necessary replicas. As a result, this method allocates replicas with low overhead and low traffic. On the other hand, since each mobile host allocates replicas based on only the access frequencies to data items, mobile hosts with the same access characteristics allocate the same replicas. However, a mobile host can access data items or replicas held by other connected mobile hosts, and thus it is more effective to share many kinds of replicas among them. Therefore, the SAF method gives low data accessibility when many mobile hosts have the same or similar access characteristics.

The algorithm for this method is as follows:

I. Each machine will create a message.

II. Declare and initialize an array P[N][N] to zero, where N is the number of machines.

III. Send that message to all other machines in the system.

IV. Whenever a machine j receives a message from machine i then, increment P[i][j] by 1.

V. Divide all values of P[ ][ ] by 10.

VI. Apply bubble sort algorithm to each column of the array P[ ][ ] in descending order.

VII. For each column j, Select the first 2 items which are not the original owner of data (ie. j), they are the replicas for that machine j.

Table 1: Access frequencies table of six macines using OMNeT++

The Table 1 shows the access frequencies of 6 machines and the output of the SAF algorithm. The numbers above each machine in Figure 2 shows the replicas allocated for them.

Figure 2: The allocated replicas on each of the machines

Figure 3: The flowchart of SAF method

vi. The time stamping Property:

There is a timestamp associated with each message. This specifies how much time the message should present in the network. This is used to avoid the duplication of messages in the network. If this property is not used, then there will be more than one message with the same name in the network, which will lead to duplication. Since there can be more frequent number of disconnections occurring in ad-hoc network, these types of duplications will occur in a regular basis.

There are 2 commonly used methods to implement this duplication avoidance. They are:

· Hop Counter method

· Time Stamping Method

In hop counter method, there will be a counter which will be incremented every time a message is being forwarded. There will be dead line value and when a message exceeds this limit, it will get deleted. The disadvantage of this method is that we need a counter for each message and it need to be updated every time a message is being forwarded.

When a message is created the creation time of that will be stored. Then when the timestamp or when that time expires, the message will be deleted. The advantage of time stamping method is that we don’t have to update the counter every time a message is being forwarded.

VII. SIMULATION EXPERIMENTS:

The experiments are simulate using OMNeT++, a network simulator. Visual Basic and Turbo C++ are also used to assist OMNeT++ in simulation.

There are so many observations that are being made based on the simulation results. There are so many runs made on the simulated system by changing the parameter values and recording the results. They are as follows:

1. Number of machines Vs Simulation time:

This result shows how the simulation time is affected by the number of machines. We have made 6 runs in the system by varying the number of machines from 1 to 6. The simulation time is increasing in a non-uniform fashion according to an increase in the number of machines as shown in Figure 4.